package search;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 在一个有序数组中，由多个相同的值时，如何将所有的数值都找到，而不是返回其中一个
 */
public class BinarySearchImprove {
    // 增加一个counts 看执行了多少次
    private static int counts = 0;
    public static void main(String[] args) {
        int[] arr = {0,1,2,3,4,6,6,7,7,7,7,8,9,9,9,9,9,9,9,9,9,9};
        ArrayList<Integer> arrayList = binarySearch(arr, 0, arr.length - 1, 0);
        System.out.println(arrayList);
        System.out.println(counts+"次");
    }

    /**
     *完成一个课后习题：在一个有序数组中，由多个相同的值时，如何将所有的数值都找到，而不是返回其中一个。
     *思路分析
     *      1）在找到mid索引值，不要马上返回
     *      2）向mid索引值的左边扫描，将所有满足1000的元素的下标，加入到ArrayList中
     *      3）向mid索引值的右边扫描，将所有哦满足1000的元素的下标，加入到arrayList中
     *      4）返回arraylist
     * @return
     */
    private static ArrayList<Integer> binarySearch(int[]arr, int left, int right, int value){
        counts++;
        ArrayList<Integer> list = new ArrayList<>();
        int mid = left + (right-left)/ 2;
        while(left<=right){
            if (arr[mid]>value){
                return binarySearch(arr,left,mid-1,value);
            }else if(arr[mid]<value){
                return binarySearch(arr,mid+1,right,value);
            }else {
                // else 条件中找到了value, 因为arr是有序的，我们只需要向左右遍历查看还有没有相同的值
                int temp = mid-1;
                while (temp >=0&& arr[temp]==value ){
                    list.add(temp);
                    temp --;
                }
                temp = mid+1;
                while (temp <arr.length && arr[temp]==value ){
                    list.add(temp);
                    temp ++;
                }
                list.add(mid);
                 Collections.sort(list);
                 return list;
            }
        }
        // left > right 未找到情况
        return list;
    }
}
